package jianzhioffer;

/**
 * 变态跳台阶
 * 青蛙可以一步跳 1~n 任意高的台阶，求跳上n级台阶有多少跳法
 *
 * 注意：还要加上从开始直接跳到n的情况，所以在最后要+1
 * 递推公式: p[n] = p[n-1] + p[n-2] ... p[1] + 1
 *
 * Created by yzy on 2019-12-26 17:59
 */
public class JumpFloorII {

    public static void main(String[] args) {
        int target = 3;
        System.out.println(jumpFloorII(target));
    }

    public static int jumpFloorII(int target) {
        if(target <= 2){
            return target;
        }
        int[] arr = new int[target];
        arr[0] = 1;
        arr[1] = 2;
        int idx = 2;
        while(idx < target){
            int val = 0;
            for(int i=0; i<idx; i++){
                val +=arr[i];
            }
            arr[idx] = val + 1;
            idx++;
        }
        return arr[target-1];
    }
}
